The Chinese remainder theorem is a result about congruences in number theory and its generalizations in abstract algebra.
In its most basic form it concerned with determining n, given the remainders generated by division of n by several numbers. For example what is the single lowest number if repeatedly divided by 3 gives a remainder of 2; when divided by 5 gives a remainder of 3; and when divided by 7 gives a remainder of 2?
Contents |
The original form of the theorem, contained in a third-century AD book Sun Zi suanjing (孫子算經 The Mathematical Classic by Sun Zi) by Chinese mathematician Sun Tzu and later republished in a 1247 book by Qin Jiushao, the Shushu Jiuzhang (數書九章 Mathematical Treatise in Nine Sections) is a statement about simultaneous congruences (see modular arithmetic).
Suppose n1, n2, …, nk are positive integers which are pairwise coprime. Then, for any given sequence of integers a1,a2, …, ak, there exists an integer x solving the following system of simultaneous congruences.
Furthermore, all solutions x of this system are congruent modulo to the product N = n1n2…nk.
Hence for all , if and only if
Sometimes, the simultaneous congruences can be solved even if the ni's are not pairwise coprime. A solution x exists if and only if:
All solutions x are then congruent modulo the least common multiple of the ni.
Sun Zi's work contains neither a proof nor a full algorithm. What amounts to an algorithm for solving this problem was described by Aryabhata (6th century; see Kak 1986). Special cases of the Chinese remainder theorem were also known to Brahmagupta (7th century), and appear in Fibonacci's Liber Abaci (1202).
A modern restatement of the theorem in the algebraic language is that for a positive integer with prime factorization we have the isomorphism between a ring and the direct product of its prime power parts:
Existence can be seen by an explicit construction of . We will use the notation to denote the inverse of , it is defined exactly when and are coprime - the following construction explains why the coprimality condition is needed.
Given the system (corresponding to )
Since , we have from Bézout's identity
Multiplying both sides by , we get
If we take the congruence modulo for the right-hand-side expression, it is readily seen that
But we know that
thus this suggests that the coefficient of the first term on the right-hand-side expression should be . Similarly, we can show that the coefficient of the second term should be .
We can now define the value
and it is seen to satisfy both congruences by reducing. For example
The same type of construction works in the general case of congruence equations. Let be the product of every modulus then define
and this is seen to satisfy the system of congruences by a similar calculation as before.
The following algorithm only applies if the 's are pairwise coprime. (For simultaneous congruences when the moduli are not pairwise coprime, the method of successive substitution can often yield solutions.)
Suppose, as above, that a solution is required for the system of congruences:
Again, to begin, the product is defined. Then a solution x can be found as follows.
For each i the integers and are coprime. Using the extended Euclidean algorithm we can find integers and such that . Then, choosing the label , the above expression becomes:
Consider . The above equation guarantees that its remainder, when divided by , must be 1. On the other hand, since it is formed as , the presence of N guarantees that it's evenly divisible by any so long as .
Because of this, combined with the multiplication rules allowed in congruences, one solution to the system of simultaneous congruences is:
For example, consider the problem of finding an integer x such that
Using the extended Euclidean algorithm for x modulo 3 and 20 [4×5], we find (−13) × 3 + 2 × 20 = 1, i.e. e1 = 40. For x modulo 4 and 15 [3×5], we get (−11) × 4 + 3 × 15 = 1, i.e. e2 = 45. Finally, for x modulo 5 and 12 [3×4], we get 5 × 5 + (−2) × 12 = 1, i.e. e3 = −24. A solution x is therefore 2 × 40 + 3 × 45 + 1 × (−24) = 191. All other solutions are congruent to 191 modulo 60, [3 × 4 × 5 = 60] which means that they are all congruent to 11 modulo 60.
NOTE: There are multiple implementations of the extended Euclidean algorithm which will yield different sets of , , and . These sets however will produce the same solution i.e. (-20)2+(-15)3+(-24)1=-109=11 modulo 60.
For a principal ideal domain R the Chinese remainder theorem takes the following form: If u1, ..., uk are elements of R which are pairwise coprime, and u denotes the product u1...uk, then the quotient ring R/uR and the product ring R/u1R× ... × R/ukR are isomorphic via the isomorphism
such that
This map is well-defined and an isomorphism of rings; the inverse isomorphism can be constructed as follows. For each i, the elements ui and u/ui are coprime, and therefore there exist elements r and s in R with
Set ei = s u/ui. Then the inverse of f is the map
such that
Note that this statement is a straightforward generalization of the above theorem about integer congruences: the ring Z of integers is a principal ideal domain, the surjectivity of the map f shows that every system of congruences of the form
can be solved for x, and the injectivity of the map f shows that all the solutions x are congruent modulo u.
The general form of the Chinese remainder theorem, which implies all the statements given above, can be formulated for commutative rings and ideals. If R is a commutative ring and I1, ..., Ik are ideals of R which are pairwise coprime (meaning that for all ), then the product I of these ideals is equal to their intersection, and the quotient ring R/I is isomorphic to the product ring R/I1 x R/I2 x ... x R/Ik via the isomorphism
such that
Here is a version of the theorem where R is not required to be commutative:
Let R be any ring with 1 (not necessarily commutative) and be pairwise coprime 2-sided ideals. Then the canonical R-module homomorphism is onto, with kernel . Hence, (as R-modules).
The Chinese remainder theorem does not hold in the non-commutative case. Consider the ring R of non-commutative real polynomials in x and y. Let I be the principal two-sided ideal generated by x and J the principal two-sided ideal generated by Then but
Observe that I is formed by all polynomials with an x in every term and that every polynomial in J vanishes under the substitution . Consider the polynomial . Clearly . Define a term in R as an element of the multiplicative monoid of R generated by x and y. Define the degree of a term as the usual degree of the term after the substitution . On the other hand, suppose . Observe that a term in q of maximum degree depends on y otherwise q under the substitution can not vanish. The same happens then for an element . Observe that the last y, from left to right, in a term of maximum degree in an element of is preceded by more than one x. (We are counting here all the preceding xs. e.g. in the last y is preceded by xs.) This proves that since that last y in a term of maximum degree () is preceded by only one x. Hence .
On the other hand, it is true in general that implies . To see this, note that , while the opposite inclusion is obvious. Also, we have in general that, provided are pairwise coprime two-sided ideals in R, the natural map
is an isomorphism. Note that can be replaced by a sum over all orderings of of their product (or just a sum over enough orderings, using inductively that for coprime ideals ).